/*
 * @lc app=leetcode.cn id=416 lang=cpp
 *
 * [416] 分割等和子集
 */

// @lc code=start
class Solution
{
public:
  bool canPartition(vector<int>& nums)
  {
    int n = nums.size(), sum = 0;
    for (int& num : nums)
      sum += num;
    if (sum % 2)
      return false;
    int capacity = sum / 2;
    // dp[i] 背包容量为i时能获得的最大价值，价值 = 重量 = nums[j] 0 <= j < n
    vector<int> dp(capacity + 1);
    for (int i = 0; i < n; ++i) {
      for (int j = capacity; j >= nums[i]; --j)
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
    return dp[capacity] == capacity;
  }
};
// @lc code=end
